package datastructure.stack02;


import org.junit.jupiter.api.Test;

/**
 * 栈操作
 *
 * @Filename: StackTest
 * @Author: czh
 * @Data:2023/1/3 11:40
 * 后进先出、先进后出
 * 数组栈和链表栈
 */
public class StackTest {
    /**
     * 数组栈的操作
     */
    @Test
    public void TestArrayStack() {
        ArrayStack arrayStack = new ArrayStack(5);
        arrayStack.push("A");
        arrayStack.push("B");
        arrayStack.push("C");
        arrayStack.push("D");
        arrayStack.push("E");
        arrayStack.display();
        // 出栈操作
        arrayStack.pop();
        arrayStack.display();
        arrayStack.push("F");
        // 获取栈顶元素
        System.out.println(arrayStack.peek());
    }

    /**
     * 链表栈的操作
     */
    @Test
    public void testLinkStack() {
        LinkListStack linkListStack = new LinkListStack();
        linkListStack.push("A");
        linkListStack.push("B");
        linkListStack.push("C");
        linkListStack.push("D");
        linkListStack.display();
        // 出栈
        linkListStack.pop();
        linkListStack.display();
    }
}

/**
 * 数组栈的基本操作
 */
class ArrayStack {
    String[] data;
    int size;
    // 栈顶位置
    int top = -1;

    // 构造器
    public ArrayStack(int size) {
        this.size = size;
        this.data = new String[size];
    }

    /**
     * 添加元素
     */
    public boolean push(String value) {
        // 栈满
        if (this.top >= this.size - 1) {
            throw new RuntimeException("栈满");
        }
        this.top++;
        this.data[top] = value;
        return true;
    }

    /**
     * 弹出栈顶元素
     */
    public String pop() {
        if (this.top == -1) {
            return null;
        }
        String result = this.data[this.top];
        this.top--;
        return result;
    }

    /**
     * 获取栈顶元素
     */
    public String peek() {
        if (this.top == -1) {
            return null;
        }
        return this.data[this.top];
    }

    /**
     * 遍历栈元素
     */
    public void display() {
        if (this.top < 1) {
            System.out.println("空栈");
        } else {
            for (int i = 0; i <= this.top; i++) {
                System.out.print(this.data[i] + " ");
            }
            System.out.println();
        }
    }
}


/**
 * 链表栈的基本操作
 */
class LinkListStack {
    // 栈顶元素
    Node2 top;

    public LinkListStack() {

    }

    /**
     * 添加元素
     * 往栈中push一个数据：
     * 首先将要push的数据的next赋值为栈顶top
     * 然后将栈顶指针指向新push进来的节点
     *
     * @param obj
     * @return
     */
    public void push(Object obj) {
        Node2 newNode = new Node2(obj);
        newNode.next = top;
        top = newNode;
    }

    /**
     * 弹出栈顶元素
     * 从栈中弹出一个数据，
     * 将栈顶指针指向弹出节点的下一个
     */
    public Object pop() {
        if (top == null) {
            return null;
        }
        // 删除头部节点
        Node2 node2 = this.top;
        this.top = this.top.next;
        return node2.data;
    }

    public void display() {
        while (this.top != null) {
            System.out.print(this.top.data + " ");
            this.top = this.top.next;
        }
        System.out.println();
    }
}

// 链表的节点类
class Node2 {
    // 每个节点的数据
    public Object data;
    // 每个节点指向下一个节点的连接
    public Node2 next; // 指向下一个节点

    // 构造器
    public Node2(Object data) {
        this.data = data;
    }

    // 构造器
    public Node2(Object data, Node2 next) {
        this.data = data;
        this.next = next;
    }
}